COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002
C00009 ENDMK
C⊗;


.RIGHT MARGIN 72
.LOWER CASE.FLAG CAPITALIZE

1.0##<INTRODUCTION
.SKIP 2
↑IT IS WELL KNOWN THAT TAIL-RECURSIVE PROCEDURES (<TR FOR SHORT)
ARE FORMALLY EQUIVALENT TO ITERATIVE PROCEDURES [1].
↑UNFORTUNATELY, WHEN INTERPRETED, <TR CODE BEHAVES AS ORDINARY
RECURSIVE CODE, AND WE DO NOT OBTAIN THE BENEFIT  OF THE FORMAL 
EQUIVALENCE. ↑WE NEED A WAY TO MAKE THE FORMAL EQUIVALENCE ALSO
A PRACTICAL ONE.
.SKIP 1

↑THE PROBLEM OF THE COMPUTATION OF <TR PROCEDURES CAN BE STATED IN
TERMS OF PROGRAM TRANSFORMATIONS, OR IN TERMS OF INTERPRETERS
SPECIALLY DESIGNED TO HANDLE THEM PROPERLY.
.SKIP 1
↑STATIC PROGRAM TRANSFORMATIONS [4,10] FROM <TR TO ITERATIVE
PROGRAMS ARE MAINLY USED ON COMPILER-ORIENTED <LISP SYSTEMS, AND
THEREFORE DO NOT ALLOW FULL ACCESS TO INTERPRETER-ORIENTED TOOLS
OF DEBUGGING, BREAKS, TRACES ETC.
↑MOREOVER, AS THEY ARE NAME-SENSITIVE, THEY CANNOT HANDLE
PROCEDURES WITH CIRCULAR TYPES.
.SKIP 1

↑INTERPRETER-ORIENTED PROCESSING OF <TR PROCEDURES USES
NON-RECURSIVE CONTROL STRUCTURES LIKE MESSAGE PASSING AS IN
↑HEWITT'S <ACTORS SYSTEM [7,8] OR GENERALIZED <FUNARG
DEVICES WITH STATIC A-LISTS, AS IN ↑SUSSMAN'S <SCHEME [12].
↑ALSO DELAYED EVALUATION OF <CONS [6] HAVE BEEN PROPOSED IN
WHICH PARTIAL BUILDING OF A STRUCTURE IS TRIGGERED BY INVOCATIONS
TO THE DECOMPOSITION PRIMITIVES <CAR AND <CDR APPLIED TO THIS
VIRTUAL STRUCTURE.
.BREAK
↑AS INTERESTING AS THEY ARE, THERE DO NOT SEEM TO BE ANY EVIDENT
WAYS TO ADAPT SUCH METHODS TO ORDINARY RECURSIVE STACK-ORIENTED
<LISP INTERPRETERS.
.SKIP 1
↑IN CONTRAST,WE PROPOSE A SIMPLE WAY TO PROCESS <TR PROCEDURES
ITERATIVELY, WITHOUT ANY PROGRAM TRANSFORMATIONS OR NON-RECURSIVE
CONTROL STRUCTURES. ↑OUR SCHEME CAN BE USED WITH A-LISTS AS WELL AS
VALUE-CELLS STACK-ORIENTED <LISP INTERPRETERS.


.PAGE

2.0##<TAIL-RECURSIVE <SCHEMATA
.SKIP 2
↑IN [1], A <TR SCHEMA IN ITERATIVE FORM IS DEFINED AS A RECURSION
EQUATION
.SKIP 1
.NOFILL
      F(X1, ... ,XN) = G(F,X1, ... ,XN,H1, ... ,HM)
.FILL

.SKIP 1
WHERE G IS A CONDITIONAL EXPRESSION DEFINING F IN TERMS OF THE
FUNCTIONS H1,...,HM;G IS SAID TO BE ITERATIVE IF F OCCURS EXACTLY
IN TERMS OF G IN THE FORM <THEN F(...) OR <ELSE F(...).
.BREAK
↑FOR EXAMPLE, THIS IS THE RECURSIVE FORM OF THE WELL-KNOWN

PROGRAM FOR ADDITION (<NOTE 1)
.SKIP 1
.NOFILL
      (DE PLUS (X Y) (IF (= X 0) Y
                         (ADD1 (PLUS (SUB1 X) Y))))
.FILL
.SKIP 1
AND THIS IS THE CORRESPONDING ITERATIVE FORM
.BREAK
.SKIP 1
.NOFILL
      (DE PLUS (X Y) (IF (= X 0) Y
                         (PLUS (SUB1 X) (ADD1 Y))))
.FILL
.SKIP 1

↑WE MUST GENERALIZE THE PREVIOUS DEFINITION OF ITERATIVE SCHEMA
TO ANY NAMED #-EXPRESSION SUCH THAT
.SKIP 1
.NOFILL
(1)  F = ( (X1 ... XN) ... (F A1 ... AN))      (<NOTE 2)
.FILL
.SKIP 1
I.E. THE LAST TERM OF THE #-EXPRESSION BODY IS A CALL OF THIS
#-EXPRESSION.
.SKIP 1
.NOFILL
(2)  F = ( (X1 ... XN) ... (IF C (F A1 ... AN) ...))  
     AND
     F = ( (X1 ... XN) ... (IF C E1 E2 ... (F A1 ... AN)))
.FILL
.SKIP 1
I.E. THE <THEN-\P\A\R\T OR THE LAST TERM OF THE <ELSE-\P\A\R\T OF
AN IF-FORM IS A CALL OF THIS #-EXPRESSION.
.BREAK
↑NESTED IF-FORMS ARE VALID UNDER THIS SCHEMA, E.G.
.SKIP 1
.NOFILL

      F = ( (X1...XN) ... (IF C1 (IF C2 ... (IF CK (F A1...AN) ... ))))
.FILL
.SKIP 1
.NOFILL
(3)   F = ( (X1...XN) ... (COND ... (C E1 ... EM-1 (F A1...AN)) ... ))
.FILL
.SKIP 1
↑NOTE THAT THE CONDITION C, EVEN IF IT CONSISTS SOLELY OF THE CONSTANT
<T , MUST MENTIONNED EXPLICITELY, IN CONTRAST WITH, FOR EXAMPLE ,
<INTERLISP [13] STYLE OF WRITING <COND\S.

.SKIP 1
<NOTE 1: (IF C E1 E2 ... EN IS THE <LISP EQUIVALENT TO THE FORM
.BREAK
.NOFILL
         IF C THEN E1 ELSE E2; ... ;EN FI .
.FILL
.SKIP 1
<NOTE 2: ↑THIS PART OF THE DEFINITION MEANS THAT WE ALLOW
NON-TERMINATING PROCEDURES.
.PAGE